package 岛屿问题;

import java.util.Scanner;

/**
 * @author: AirMan
 * @date: 2025/6/3 19:51
 * @description:
 * 现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。
 * 矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
 * 矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，
 * 但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，
 * 从这些单元格出发的水可以达到第一组边界和第二组边界。
 * 输入描述：
 * 第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。
 * 后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度
 */
public class Solution6 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // 寻找符合条件的节点
        // 采用dfs遍历，出发点为第一边界，逆流而上标记访问过的节点
        // 然后出发点为第二边界，逆流而上再次编辑访问过的点
        // 当一个节点被标记两次（一次是从第一边界出发的，另一次是从第二边界出发的），那么就说明这个点能同时到达两个边界
        boolean[][] visited1 = new boolean[n][m];
        // 从第一边界出发
        for (int j = 0; j < m; j++) {
            if (!visited1[0][j]) {
                dfs(graph, visited1, 0, j, 0);
            }
        }
        for (int i = 0; i < n; i++) {
            if (!visited1[i][0]) {
                dfs(graph, visited1, i, 0, 0);
            }
        }
        // 从第二边界出发
        boolean[][] visited2 = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            if (!visited2[i][m - 1]) {
                dfs(graph, visited2, i, m - 1, 0);
            }
        }
        for (int j = 0; j < n; j++) {
            if (!visited2[n - 1][j]) {
                dfs(graph, visited2, n - 1, j, 0);
            }
        }
        // 查看哪一个点同时被访问过两次
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (visited1[i][j] && visited2[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
    }

    private static void dfs(int[][] graph, boolean[][] visited, int x, int y, int preheight) {
        // 遇到边界或者访问过的点，直接返回
        if (x < 0 || x >= graph.length || y < 0 || y >= graph[0].length || visited[x][y]) return;
        // 不满足水流条件也直接返回
        if (graph[x][y] < preheight) return;
        // 满足条件就继续遍历
        visited[x][y] = true;
        // 往四个方向进行 dfs 遍历
        int nowHeight = graph[x][y];
        dfs(graph, visited, x - 1, y, nowHeight); // left
        dfs(graph, visited, x + 1, y, nowHeight); // right
        dfs(graph, visited, x, y + 1, nowHeight); // above
        dfs(graph, visited, x, y - 1, nowHeight); // below
    }
}
